home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / libgutil / tomesh.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  23KB  |  997 lines
  1. /*
  2.  * Copyright 1991, 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /*
  18.  *    tomesh - 
  19.  *        Convert independent triangles to large triangle meshes
  20.  *
  21.  *                Kurt Akeley - 24 March 1988
  22.  *                     Paul Haeberli - 1990    
  23.  *               Derrick Burns - September 1990
  24.  *
  25.  *
  26.  *    The algorithm attempts to avoid leaving isolated triangles by
  27.  *    choosing as the next triangle in a growing mesh that adjacent
  28.  *    triangle with the minimum number of neighbors.  It will frequently
  29.  *    produce a single, large mesh for a well behaved set of triangles.
  30.  *
  31.  *    To use, include the file mesh.h.
  32.  *
  33.  *    exports four routines:    
  34.  *
  35.  *        Meshobj *newMeshobj( ... )
  36.  *        void in_ambegin( Meshobj * )
  37.  *        void in_amnewtri( Meshobj * )
  38.  *        void in_amvert( Meshobj *, long )
  39.  *        void in_amend( Meshobj * )
  40.  *        void freeMeshobj( Meshobj * )
  41.  *
  42.  *    calls back these routines:    
  43.  *        void out_ambegin( long nverts, long ntris )
  44.  *        void out_amend( void );
  45.  *         int out_amhashvert( long v )
  46.  *        int out_amvertsame( long v1, long v2 )
  47.  *        void out_amvertdata( long fptr )
  48.  *        void out_ambgntmesh( void ) 
  49.  *        void out_amendtmesh( void ) 
  50.  *        void out_amswaptmesh( void ) 
  51.  *        void out_amvert( long index )
  52.  *
  53.  *    on output the package calls:
  54.  *    
  55.  *    void out_ambegin( long nverts, long ntris )
  56.  *    calls repeatedly:
  57.  *        int out_amhashvert( long v )
  58.  *        int out_amvertsame( long v1, long v2 )
  59.  *    calls nverts times:
  60.  *        void out_amvertdata( long fptr )
  61.  *    calls these in mixed sequence:
  62.  *        void out_ambgntmesh( void ) 
  63.  *          void out_amvert( long index )
  64.  *          void out_amswaptmesh( void )
  65.  *        void out_amendtmesh( void ) 
  66.  *    void out_amend()
  67.  */
  68.  
  69. #include <stdlib.h>
  70. #include <stdio.h>
  71. #include "mesh.h"
  72.  
  73. #define dprintf        if( 0 ) (void) printf
  74. #define FALSE        0
  75. #define TRUE        1
  76. #define VERTHASHSIZE    9991
  77. #define TRIHASHSIZE    9991
  78. #define EDGEHASHSIZE    9991
  79. #define INITMESH    replaceB = FALSE
  80. #define SWAPMESH    replaceB = !replaceB
  81. #define REPLACEVERT(v)    {vert[replaceB] = (v); SWAPMESH;}
  82.  
  83. typedef struct Vert {
  84.     struct Vert *next;
  85.     struct Vert *prev;
  86.     struct Vert *hnext;
  87.     long id, index;
  88. } Vert;
  89.  
  90. typedef struct Vertlist {
  91.     Vert *first,*last;
  92. } Vertlist;
  93.  
  94. typedef struct Edge {
  95.     struct Edge *hnext;
  96.     struct Tri *tri;
  97.     long index0, index1;
  98. } Edge;
  99.  
  100. typedef struct Tri {
  101.     struct Tri *next;
  102.     struct Tri *prev;
  103.     struct Tri *hnext;
  104.     struct Tri *(adj[3]);
  105.     Vert *vert[3];
  106.     int drawvert[3];
  107.     int adjcount;
  108.     int used;
  109. } Tri;
  110.  
  111. typedef struct Trilist {
  112.     Tri *first,*last;
  113. } Trilist;
  114.  
  115. /* local functions */
  116. static Tri *    hashtrifind( Meshobj *, Tri * );
  117. static Vert *    hashvertfind( Meshobj *, Vert * );
  118. static void    beginoutputobj( Meshobj *, Vert *, Tri * );
  119. static void    freelists( Meshobj * );
  120. static void    hashedgebegin( Meshobj *, int );
  121. static void    hashedgeadd( Meshobj *, Tri *, Vert *, Vert * );
  122. static Edge *    hashedgefind( Meshobj *, Vert *, Vert * );
  123. static void    hashedgeend( Meshobj * );
  124. static void    hashtriadd( Meshobj *, Tri * );
  125. static void    hashtribegin( Meshobj * );
  126. static void    hashtriend( Meshobj * );
  127. static int    hashvert( Meshobj *, Vert * );
  128. static void    hashvertadd( Meshobj *, Vert* );
  129. static void    hashvertbegin( Meshobj * );
  130. static void    hashvertend( Meshobj * );
  131. static void    makelists( Meshobj * );
  132. static void    outmesh( Meshobj *, Trilist * );
  133. static void    removeadjacencies( Meshobj *, Tri * );
  134.  
  135. static Tri *    maketri( void ) ;
  136. static Tri *    minadj( Tri * );
  137. static Trilist *maketrilist( void ) ;
  138. static Vert *    makevert( void ) ;
  139. static Vertlist *makevertlist( void );
  140. static int    hashedge( long, long );
  141. static int    hashtri( Tri * );
  142. static int    ismember( Vert *, Tri * );
  143. static int    notcommon( Tri *, Tri * );
  144. static int    triequal( Tri *, Tri * ) ;
  145. static void    deletetri( Trilist *, Tri * );
  146. static void    freetri( Tri * );
  147. static void    freetrilist( Trilist * );
  148. static void    freevert( Vert * );
  149. static void    freevertlist( Vertlist * );
  150. static void    inserttri( Trilist *, Tri * );
  151. static void    insertvert( Vertlist *, Vert * );
  152.  
  153. Meshobj *
  154. newMeshobj ( 
  155.     void    (*out_ambegin)( int, int ),
  156.     void    (*out_amend)( void ),
  157.     int        (*out_amhashvert)( long ),
  158.     int        (*out_amvertsame)( long, long ),
  159.     void    (*out_amvertdata)( long ),
  160.     void    (*out_ambgntmesh)( void ),
  161.     void    (*out_amendtmesh)( void ),
  162.     void    (*out_amswaptmesh)( void ),
  163.     void    (*out_amvert)( long ) )
  164. {
  165.     Meshobj *m;
  166.  
  167.     m            = (Meshobj *) mymalloc( sizeof(Meshobj) );
  168.     m->connectcount    = 0;
  169.     m->independentcount    = 0;
  170.     m->ambegin        = out_ambegin;
  171.     m->amend        = out_amend;
  172.     m->amhashvert    = out_amhashvert;
  173.     m->amvertsame    = out_amvertsame;
  174.     m->amvertdata    = out_amvertdata;
  175.     m->ambgntmesh    = out_ambgntmesh;
  176.     m->amendtmesh    = out_amendtmesh;
  177.     m->amswaptmesh    = out_amswaptmesh;
  178.     m->amvert        = out_amvert;
  179.     return m;
  180. }
  181.  
  182. void
  183. freeMeshobj( Meshobj *m )
  184. {
  185.     free( m );
  186. }
  187.  
  188. /* 
  189.  *    Vertex hashing
  190.  *
  191.  */
  192. static void hashvertbegin( Meshobj *m )
  193. {
  194.     int i;
  195.  
  196.     m->verthashlist = (Vert**)mymalloc(VERTHASHSIZE*sizeof(Vert*));
  197.     for(i=0; i<VERTHASHSIZE; i++) 
  198.     m->verthashlist[i] = 0;
  199. }
  200.  
  201. static int hashvert( Meshobj *m, Vert *vert )
  202. {
  203.     long val;
  204.  
  205.     val = (*m->amhashvert)(vert->id);
  206.     return val%VERTHASHSIZE;
  207. }
  208.  
  209. static Vert *hashvertfind( Meshobj *m, Vert *vert )
  210. {
  211.     int pos;
  212.     Vert *vptr;
  213.  
  214.     pos = hashvert(m,vert);
  215.     for( vptr = m->verthashlist[pos]; vptr; vptr = vptr->hnext )
  216.     if((*m->amvertsame)(vert->id,vptr->id)) 
  217.         return vptr;
  218.     return 0;
  219. }
  220.  
  221. static void hashvertadd( Meshobj *m, Vert* vert )
  222. {
  223.     int pos;
  224.  
  225.     pos = hashvert(m,vert);
  226.     vert->hnext = m->verthashlist[pos];
  227.     m->verthashlist[pos] = vert;
  228. }
  229.  
  230. static void hashvertend( Meshobj *m )
  231. {
  232.     free(m->verthashlist);
  233. }
  234.  
  235. /* 
  236.  *    Triangle hashing
  237.  *
  238.  */
  239. static void hashtribegin( Meshobj *m )
  240. {
  241.     int i;
  242.  
  243.     m->trihashlist = (Tri**)mymalloc(TRIHASHSIZE*sizeof(Tri*));
  244.     for(i=0; i<TRIHASHSIZE; i++) 
  245.     m->trihashlist[i] = 0;
  246. }
  247.  
  248. static int hashtri( Tri *tri )
  249. {
  250.     long val, l;
  251.  
  252.     l = (long)tri->vert[0];
  253.     val = l;
  254.     l = (long)tri->vert[1];
  255.     val = val^l;
  256.     l = (long)tri->vert[2];
  257.     val = val^l;
  258.     return val%TRIHASHSIZE;
  259. }
  260.  
  261. static Tri *hashtrifind( Meshobj *m, Tri *tri )
  262. {
  263.     int pos;
  264.     Tri *tptr;
  265.  
  266.     pos = hashtri(tri);
  267.     for( tptr = m->trihashlist[pos]; tptr; tptr = tptr->hnext ) 
  268.     if(triequal(tri,tptr)) 
  269.         return tptr;
  270.     return 0;
  271. }
  272.  
  273. static void hashtriadd( Meshobj *m, Tri *tri )
  274. {
  275.     int pos;
  276.  
  277.     pos = hashtri(tri);
  278.     tri->hnext = m->trihashlist[pos];
  279.     m->trihashlist[pos] = tri;
  280. }
  281.  
  282. static void hashtriend( Meshobj *m )
  283. {
  284.     free(m->trihashlist);
  285. }
  286.  
  287. /* 
  288.  *    Edge hashing
  289.  *
  290.  */
  291. static void hashedgebegin( Meshobj *m, int np )
  292. {
  293.     int i;
  294.  
  295.     m->edgehashlist = (Edge**)mymalloc(EDGEHASHSIZE*sizeof(Edge*));
  296.     m->edgearray = m->freeedges = (Edge*)mymalloc(3*np*sizeof(Edge));
  297.     for(i=0; i<EDGEHASHSIZE; i++) 
  298.     m->edgehashlist[i] = 0;
  299. }
  300.  
  301. static int hashedge( long index0, long index1 )
  302. {
  303.     long val;
  304.  
  305.     val = index0*index1;
  306.     val = val&0x7fffffff;
  307.     return val%EDGEHASHSIZE;
  308. }
  309.  
  310. static Edge *hashedgefind( Meshobj *m, Vert *v0, Vert *v1 )
  311. {
  312.     int pos;
  313.     long index0, index1;
  314.     Edge *tptr;
  315.  
  316.     index0 = v0->index;
  317.     index1 = v1->index;
  318.     pos = hashedge(index0,index1);
  319.     tptr = m->edgehashlist[pos];
  320.     return tptr;
  321. }
  322.  
  323. static void hashedgeadd( Meshobj *m, Tri *tri, Vert *v0, Vert *v1 )
  324. {
  325.     int pos;
  326.     long index0, index1;
  327.     Edge *edge;
  328.  
  329.     index0 = v0->index;
  330.     index1 = v1->index;
  331.     pos = hashedge(index0,index1);
  332.     edge = m->freeedges++;
  333.     edge->index0 = index0;
  334.     edge->index1 = index1;
  335.     edge->tri = tri;
  336.     edge->hnext = m->edgehashlist[pos];
  337.     m->edgehashlist[pos] = edge;
  338. }
  339.  
  340. static void hashedgeend( Meshobj *m )
  341. {
  342.     free(m->edgehashlist);
  343.     free(m->edgearray);
  344. }
  345.  
  346. static Vertlist *makevertlist( void ) 
  347. {
  348.     /* allocate space for and initialize a vert list */
  349.     Vertlist *tmp;
  350.  
  351.     if ((tmp=(Vertlist*)mymalloc(sizeof(Vertlist)))==0) {
  352.     (void) fprintf(stderr,"makevertlist: out of memory.  abort.\n");
  353.     exit(1);
  354.     }
  355.     tmp->first = tmp->last = 0;
  356.     return tmp;
  357. }
  358.  
  359. static void freevertlist( Vertlist *vl )
  360. {
  361.     Vert *vert, *nvert;
  362.  
  363.     for( vert = vl->first; vert; vert = nvert ) {
  364.     nvert = vert->next;
  365.     freevert(vert);
  366.     }
  367.     free(vl);
  368. }
  369.  
  370. static Trilist *maketrilist( void ) 
  371. {
  372.     /* allocate space for and initialize a tri list */
  373.     Trilist *tmp;
  374.  
  375.     if ((tmp=(Trilist*)mymalloc(sizeof(Trilist)))==0) {
  376.     (void) fprintf(stderr,"maketrilist: out of memory.  abort.\n");
  377.     exit(1);
  378.     }
  379.     tmp->first = tmp->last = 0;
  380.     return tmp;
  381. }
  382.  
  383. static void freetrilist( Trilist *tl )
  384. {
  385.     Tri *tri, *ntri;
  386.  
  387.     for( tri = tl->first; tri; tri = ntri ) {
  388.     ntri = tri->next;
  389.     freetri(tri);
  390.     }
  391.     free(tl);
  392. }
  393.  
  394. static Vert *makevert( void ) 
  395. {
  396.     /* allocate space for and initialize a vert */
  397.     Vert *tmp;
  398.  
  399.     if ((tmp=(Vert*)mymalloc(sizeof(Vert)))==0) {
  400.     (void) fprintf(stderr,"makevert: out of memory.  abort.\n");
  401.     exit(1);
  402.     }
  403.     tmp->prev = tmp->next = 0;
  404.     tmp->index = 0;
  405.     return tmp;
  406. }
  407.  
  408. static void freevert( Vert *v )
  409. {
  410.     free(v);
  411. }
  412.  
  413. static Tri *maketri( void ) 
  414. {
  415.     /* allocate space for and initialize a tri */
  416.     Tri *tmp;
  417.     int i;
  418.  
  419.     if ((tmp=(Tri*)mymalloc(sizeof(Tri)))==0) {
  420.     (void) fprintf(stderr,"maketri: out of memory.  abort.\n");
  421.     exit(1);
  422.     }
  423.     tmp->prev = tmp->next = 0;
  424.     for (i=0; i<3; i++) {
  425.     tmp->adj[i] = 0;
  426.     tmp->vert[i] = 0;
  427.     }
  428.     tmp->drawvert[0] = 0;
  429.     tmp->drawvert[1] = 1;
  430.     tmp->drawvert[2] = 2;
  431.     tmp->adjcount = 0;
  432.     tmp->used = FALSE;
  433.     return tmp;
  434. }
  435.  
  436. static void freetri( Tri *tri )
  437. {
  438.     free(tri);
  439. }
  440.  
  441. static void insertvert( Vertlist *list, Vert *item )
  442. {
  443.     /* insert the new item at the top of the list */
  444.     if (list->first) {
  445.     item->next = list->first;
  446.     item->prev = 0;
  447.     item->next->prev = item;
  448.     list->first = item;
  449.     } else {
  450.     list->first = list->last = item;
  451.     item->prev = item->next = 0;
  452.     }
  453. }
  454.  
  455. static void inserttri( Trilist *list, Tri *item )
  456. {
  457.     /* insert the new item at the top of the list */
  458.     if (list->first) {
  459.     item->next = list->first;
  460.     item->prev = 0;
  461.     item->next->prev = item;
  462.     list->first = item;
  463.     } else {
  464.     list->first = list->last = item;
  465.     item->prev = item->next = 0;
  466.     }
  467. }
  468.  
  469. static void deletetri( Trilist *list, Tri *item )
  470. {
  471.     /* delete the item from the list */
  472.     if (list->first == item) {
  473.     if (list->last == item) {
  474.         /* this is the only item in the list */
  475.         list->first = list->last = 0;
  476.     } else {
  477.         /* this is the first item in the list */
  478.         list->first = item->next;
  479.         list->first->prev = 0;
  480.     }
  481.     } else if (list->last == item) {
  482.     /* this is the last item in the list */
  483.     list->last = item->prev;
  484.     list->last->next = 0;
  485.     } else {
  486.     item->prev->next = item->next;
  487.     item->next->prev = item->prev;
  488.     }
  489.     item->prev = item->next = 0;
  490. }
  491.  
  492. static int triequal( Tri *tri1, Tri *tri2 ) 
  493. {
  494.     int i, j, k;
  495.  
  496.     k = 0;
  497.     for (i=0; i<3; i++) {
  498.     for (j=0; j<3; j++) {
  499.         if (tri1->vert[i] == tri2->vert[j])
  500.         k += 1;
  501.     }
  502.     }
  503.     if (k == 3) 
  504.     return 1;
  505.     else 
  506.     return 0;
  507. }
  508.  
  509. static void makelists( Meshobj *m )
  510. {
  511.     int i;
  512.  
  513.     m->vertlist = makevertlist();
  514.     m->trilist = maketrilist();
  515.     m->newtrilist = maketrilist();
  516.     m->donetrilist = maketrilist();
  517.     for (i=0; i<4; i++)
  518.     m->adjtrilist[i] = maketrilist();
  519. }
  520.  
  521. static void freelists( Meshobj *m )
  522. {
  523.     int i;
  524.  
  525.     freevertlist(m->vertlist);
  526.     freetrilist(m->trilist);
  527.     freetrilist(m->newtrilist);
  528.     freetrilist(m->donetrilist);
  529.     for (i=0; i<4; i++)
  530.     freetrilist(m->adjtrilist[i]);
  531. }
  532.  
  533. /*
  534.  *    actual exported routines
  535.  *
  536.  *
  537.  */
  538. void in_ambegin( Meshobj *m )
  539. {
  540.  
  541.     makelists(m);
  542.  
  543.     m->vertcount = 0;
  544.     hashvertbegin( m );
  545.     m->tmpvert = makevert();
  546.     m->npolys = 0;
  547.     m->vertno = 0;
  548. }
  549.  
  550.  
  551. void in_amnewtri( Meshobj *m )
  552. {
  553.     m->vertno = 0;
  554.     m->curtri = maketri();
  555.     inserttri(m->trilist,m->curtri);
  556.     m->npolys++;
  557. }
  558.  
  559. void in_amvert( Meshobj *m, long fptr )
  560. {
  561.     Vert *vert;
  562.  
  563.     if(m->vertno > 2) {
  564.     (void) fprintf(stderr,"in_amvert: can't have more than 3 verts in triangle\n");
  565.     return;
  566.     }
  567.     m->curtri->vert[m->vertno] = 0;
  568.     m->tmpvert->id = fptr;
  569.     vert = hashvertfind(m,m->tmpvert);
  570.     if(vert)
  571.     m->curtri->vert[m->vertno] = vert;
  572.     else  {
  573.     hashvertadd(m,m->tmpvert);
  574. /* add a new vertex to the list */
  575.     m->tmpvert->index = m->vertcount;
  576.     m->vertcount++;
  577.     m->curtri->vert[m->vertno] = m->tmpvert;
  578.     insertvert(m->vertlist,m->tmpvert);
  579.     m->tmpvert = makevert();
  580.     }
  581.     m->vertno++;
  582. }
  583.  
  584. void in_amend( Meshobj *m )
  585. {
  586.     Vert *vert0,*vert1;
  587.     Tri *tri;
  588.     Tri *tmptri;
  589.     Tri *nexttri;
  590.     Edge *edge;
  591.     int i, j, k;
  592.     int degeneratecount;
  593.     int equivalentcount;
  594.     int count;
  595.     int adjcount[4];
  596.     int adjnumber;
  597.  
  598.     freevert(m->tmpvert);
  599.     if(m->vertno != 3) {
  600.     (void) fprintf(stderr,"in_amend: incomplete triangle\n");
  601.     exit(1);
  602.     }
  603.     hashvertend(m);
  604.     dprintf("%d triangles read\n",m->npolys);
  605.     dprintf("%d vertexes created\n",m->vertcount);
  606.  
  607. /*** eliminate degenerate triangles ***/
  608.     dprintf("eliminating degenerate triangles\n");
  609.     degeneratecount = 0;
  610.     for (tri=m->trilist->first; tri;) {
  611.     if ((tri->vert[0] == tri->vert[1]) ||
  612.         (tri->vert[0] == tri->vert[2]) ||
  613.         (tri->vert[1] == tri->vert[2])) {
  614.         degeneratecount += 1;
  615.         tmptri = tri->next;
  616.         deletetri(m->trilist,tri);
  617.         freetri(tri);
  618.         tri = tmptri;
  619.     } else 
  620.         tri = tri->next;
  621.     }
  622.     dprintf("%d degenerate triangles eliminated\n",degeneratecount);
  623.  
  624. /*** eliminate equivalent triangles ***/
  625.     dprintf("eliminating equivalent triangles\n");
  626.     count = 0;
  627.     equivalentcount = 0;
  628.  
  629.     hashtribegin(m);
  630.     for (tri=m->trilist->first; tri;) {
  631.     count += 1;
  632.     if(hashtrifind(m,tri)) {
  633.         equivalentcount += 1;
  634.         nexttri = tri->next;
  635.         deletetri(m->trilist,tri);
  636.         freetri(tri);
  637.         tri = nexttri;
  638.     } else {
  639.         hashtriadd(m,tri);
  640.         tri = tri->next;
  641.     }
  642.     }
  643.     hashtriend(m);
  644.     dprintf("%d equivalent triangles eliminated\n",equivalentcount);
  645.  
  646.     beginoutputobj(m,m->vertlist->first,m->trilist->first);
  647.  
  648. /*** compute triangle adjacencies ***/
  649.     dprintf("computing adjacent triangles\n");
  650.     hashedgebegin(m,m->npolys);
  651.     dprintf("adding to hash table . . ");
  652.     for (tri=m->trilist->first; tri; tri=tri->next) {
  653.     for(i=0; i<3; i++) {
  654.         vert0 = tri->vert[(i+0)%3];
  655.         vert1 = tri->vert[(i+1)%3];
  656.         hashedgeadd(m,tri,vert0,vert1);
  657.     }
  658.     }
  659.     dprintf("done\n");
  660.     count = 0;
  661.     for (tri=m->trilist->first; tri; tri=tri->next) {
  662.     count += 1;
  663.     for (i=0; i<3; i++) {
  664.         if (tri->adj[i])
  665.         continue;
  666.         vert0 = tri->vert[i];
  667.         vert1 = tri->vert[(i+1)%3];
  668.         for (edge=hashedgefind(m,vert0,vert1); edge; edge=edge->hnext) {
  669.         nexttri = edge->tri;
  670.         if(nexttri == tri) 
  671.             continue;
  672.         for (j=0; j<3; j++) {
  673.             if (vert0 == nexttri->vert[j]) {
  674.             for (k=0; k<3; k++) {
  675.                 if (k==j)
  676.                 continue;
  677.                 if (vert1 == nexttri->vert[k]) {
  678.                 switch (j+k) {
  679.                     case 1:
  680.                     adjnumber = 0;
  681.                     break;
  682.                     case 2:
  683.                     adjnumber = 2;
  684.                     break;
  685.                     case 3:
  686.                     adjnumber = 1;
  687.                     break;
  688.                     default:
  689.                     (void) fprintf(stderr,
  690.                         "ERROR: bad adjnumber\n");
  691.                     break;
  692.                 }
  693.                 if (tri->adj[i]||nexttri->adj[adjnumber]) {
  694.                 } else {    
  695.                     tri->adj[i] = nexttri;
  696.                     nexttri->adj[adjnumber] = tri;
  697.                 }
  698.                 }
  699.             }
  700.             }
  701.         }
  702.         }
  703.     }
  704.     }
  705.     hashedgeend(m);
  706.     dprintf(" done\n");
  707.  
  708. /*** test adjacency pointers for consistency ***/
  709.     for (tri=m->trilist->first; tri; tri=tri->next) {
  710.     for (i=0; i<3; i++) {
  711.         if (nexttri = tri->adj[i]) {
  712.         for (j=0,k=0; j<3; j++) {
  713.             if (tri == nexttri->adj[j])
  714.             k += 1;
  715.         }
  716.         if (k != 1) {
  717.             (void) fprintf(stderr," ERROR: %x to %x k = %d\n",tri,nexttri,k);
  718.         }
  719.         }
  720.     }
  721.     }
  722.  
  723. /*** compute adjacency statistics ***/
  724.     for (i=0; i<4; i++)
  725.     adjcount[i] = 0;
  726.     for (tri=m->trilist->first; tri;) {
  727.     for (i=0,count=0; i<3; i++) {
  728.         if (tri->adj[i])
  729.         count += 1;
  730.     }
  731.     tri->adjcount = count;
  732.     adjcount[count] += 1;
  733.     nexttri = tri->next;
  734.     deletetri(m->trilist,tri);
  735.     inserttri(m->adjtrilist[count],tri);
  736.     tri = nexttri;
  737.     }
  738.     dprintf("adjacencies: 0:%d, 1:%d, 2:%d, 3:%d\n",
  739.     adjcount[0],adjcount[1],adjcount[2],adjcount[3]);
  740.  
  741. /*** search for connected triangles and output ***/
  742.     while (1) {
  743.     /*** output singular triangles, if any ***/
  744.     while (tri = m->adjtrilist[0]->first) {
  745.         deletetri(m->adjtrilist[0],tri);
  746.         inserttri(m->newtrilist,tri);
  747.         tri->used = TRUE;
  748.         outmesh(m,m->newtrilist);
  749.     }
  750.     /*** choose a seed triangle with the minimum number of adjacencies ***/
  751.     if (tri = m->adjtrilist[1]->first)
  752.         deletetri(m->adjtrilist[1],tri);
  753.     else if (tri = m->adjtrilist[2]->first)
  754.         deletetri(m->adjtrilist[2],tri);
  755.     else if (tri = m->adjtrilist[3]->first)
  756.         deletetri(m->adjtrilist[3],tri);
  757.     else
  758.         break;
  759.     inserttri(m->newtrilist,tri);
  760.     removeadjacencies(m,tri);
  761.  
  762.     /*** extend in one direction using triangles with min adjacencies ***/
  763.     while (tri = minadj(tri)) {
  764.         deletetri(m->adjtrilist[tri->adjcount],tri);
  765.         inserttri(m->newtrilist,tri);
  766.         removeadjacencies(m,tri);
  767.     }
  768.  
  769.     /*** if seed has two or more adjacencies, extend in other direction **/
  770.     tri = m->newtrilist->first;
  771.     nexttri = 0;
  772.     for (i=0; i<3; i++) {
  773.         if (tri->adj[i] &&
  774.         (tri->adj[i] != tri->next) &&
  775.         (!(tri->adj[i]->used))) {
  776.         nexttri = tri->adj[i];
  777.         break;
  778.         }
  779.     }
  780.     for( tri = nexttri; tri; tri=minadj(tri) ) {
  781.         deletetri(m->adjtrilist[tri->adjcount],tri);
  782.         inserttri(m->newtrilist,tri);
  783.         removeadjacencies(m,tri);
  784.     }
  785.  
  786.     /*** output the resulting mesh ***/
  787.     outmesh(m,m->newtrilist);
  788.     }
  789.     if (m->connectcount)
  790.     dprintf("%d triangle mesh%s output\n",
  791.         m->connectcount,m->connectcount==1?"":"es");
  792.     if (m->independentcount)
  793.     dprintf("%d independent triangle%s output\n",
  794.         m->independentcount,m->independentcount==1?"":"s");
  795.     (*m->amend)();
  796.     freelists(m);
  797. }
  798.  
  799. static int ismember( Vert *vert, Tri *tri )
  800. {
  801.     /*** return TRUE if vert is one of the vertexes in tri, otherwise FALSE ***/
  802.     int i;
  803.  
  804.     for (i=0; i<3; i++)
  805.     if (vert == tri->vert[i])
  806.         return TRUE;
  807.     return FALSE;
  808. }
  809.  
  810. static int notcommon( Tri *tri, Tri *tri2 )
  811. {
  812.     /*** returns the index of the vertex in tri that is not in tri2 ***/
  813.     int i;
  814.  
  815.     for (i=0; i<3; i++)
  816.     if (!ismember(tri->vert[i],tri2))
  817.         return i;
  818.     return -1;
  819. }
  820.  
  821. #ifdef DEBUGXXX
  822. printlist(Trilist *tris, char *str)
  823. {
  824.     Tri *tri, *ntri;
  825.  
  826.     fprintf(stderr,"\nPRINTLIST %s\n",str);
  827.     tri = tris->first;
  828.     while(tri) {
  829.     fprintf(stderr," %d",tri);
  830.     tri = tri->next;
  831.     }
  832. }
  833. #endif
  834.  
  835. static void outmesh( Meshobj *m, Trilist *tris )
  836. {
  837.     Tri *tri;
  838.     int i;
  839.     Vert *vert[2];
  840.     Vert *nextvert;
  841.     int replaceB;
  842.  
  843.     /*** output trilist - transfer to donelist ***/
  844.     tri = tris->first;
  845.     if (tri == tris->last) {
  846.     /*** there is only one triangle in the mesh - use polygon command ***/
  847.     m->independentcount += 1;
  848.     (*m->ambgntmesh)();
  849.     (*m->amvert)(tri->vert[0]->index);
  850.     (*m->amvert)(tri->vert[1]->index);
  851.     (*m->amvert)(tri->vert[2]->index);
  852.     (*m->amendtmesh)();
  853.     deletetri(tris,tri);
  854.     inserttri(m->donetrilist,tri);
  855.     } else {
  856.     /*** a real mesh output is required ***/
  857.     m->connectcount += 1;
  858.     /*** start output with vertex that is not in the second triangle ***/
  859.     i = notcommon(tri,tri->next);
  860.     INITMESH;
  861.     (*m->ambgntmesh)();
  862.     (*m->amvert)(tri->vert[i]->index);
  863.     REPLACEVERT(tri->vert[i]);
  864.     (*m->amvert)(tri->vert[(i+1)%3]->index);
  865.     REPLACEVERT(tri->vert[(i+1)%3]);
  866.     (*m->amvert)(tri->vert[(i+2)%3]->index);
  867.     REPLACEVERT(tri->vert[(i+2)%3]);
  868.     /*** compute vertex of second triangle that is not in the first ***/
  869.     i = notcommon(tri->next,tri);
  870.     nextvert = (tri->next)->vert[i];
  871.     /*** transfer triangle to done list ***/
  872.     deletetri(tris,tri);
  873.     inserttri(m->donetrilist,tri);
  874.     for( tri = tris->first; tri->next; tri=tris->first ) {
  875.         /*** check for errors ***/
  876.         if ((!ismember(vert[0],tri)) || (!ismember(vert[1],tri)) ||
  877.         (!ismember(nextvert,tri))) {
  878.         (void) fprintf(stderr,"ERROR in mesh generation\n");
  879.         }
  880.         if ((vert[0] == vert[1]) || (vert[0] == nextvert)) {
  881.         (void) fprintf(stderr,"ERROR in mesh generation\n");
  882.         }
  883.         /*** decide whether to swap or not ***/
  884.         if (ismember(vert[replaceB],tri->next)) {
  885.         (*m->amswaptmesh)();
  886.         SWAPMESH;
  887.         }
  888.         /*** output the next vertex ***/
  889.         (*m->amvert)(nextvert->index);
  890.         REPLACEVERT(nextvert);
  891.         /*** determine the next output vertex ***/
  892.         i = notcommon(tri->next,tri);
  893.         nextvert = (tri->next)->vert[i];   
  894.         /*** transfer tri to the done list ***/
  895.         deletetri(tris,tri);
  896.         inserttri(m->donetrilist,tri);
  897.     }
  898.     /*** output the last vertex ***/
  899.     (*m->amvert)(nextvert->index);
  900.     REPLACEVERT(nextvert);
  901.     deletetri(tris,tri);
  902.     inserttri(m->donetrilist,tri);
  903.     (*m->amendtmesh)();
  904.     }
  905. }
  906.  
  907. static void removeadjacencies( Meshobj *m, Tri *tri )
  908. {
  909.     int i,j;
  910.     Tri *adjtri;
  911.  
  912.     tri->used = TRUE;
  913.     for (i=0; i<3; i++) {
  914.     adjtri = tri->adj[i];
  915.     if (adjtri) {
  916.         deletetri(m->adjtrilist[adjtri->adjcount],adjtri);
  917.         adjtri->adjcount -= 1;
  918.         for (j=0; j<3; j++) {
  919.         if (tri == adjtri->adj[j]) {
  920.             adjtri->adj[j] = 0;
  921.             break;
  922.         }
  923.         }
  924.         inserttri(m->adjtrilist[adjtri->adjcount],adjtri);
  925.     }
  926.     }
  927. }
  928.  
  929. static Tri *minadj( Tri *tri )
  930. {
  931.     int min0,min1;
  932.  
  933.     switch (tri->adjcount) {
  934.     case 0:
  935.         return 0;
  936.     case 1:
  937.         if (tri->adj[0])
  938.         return tri->adj[0];
  939.         else if (tri->adj[1])
  940.         return tri->adj[1];
  941.         else
  942.         return tri->adj[2];
  943.     case 2:
  944.         if (tri->adj[0]) {
  945.         min0 = 0;
  946.         if (tri->adj[1])
  947.             min1 = 1;
  948.         else
  949.             min1 = 2;
  950.         } else {
  951.         min0 = 1;
  952.         min1 = 2;
  953.         }
  954.         if ((tri->adj[min0])->adjcount <= (tri->adj[min1])->adjcount)
  955.         return tri->adj[min0];
  956.         else
  957.         return tri->adj[min1];
  958.     case 3:
  959.     default:
  960.         if ((tri->adj[0])->adjcount <= (tri->adj[1])->adjcount)
  961.         min0 = 0;
  962.         else
  963.         min0 = 1;
  964.         min1 = 2;
  965.         if ((tri->adj[min0])->adjcount <= (tri->adj[min1])->adjcount)
  966.         return tri->adj[min0];
  967.         else
  968.         return tri->adj[min1];
  969.     }
  970. }
  971.  
  972. static void beginoutputobj( Meshobj *m, Vert *verts, Tri *tris ) 
  973. {
  974.     Vert *vert;
  975.     Tri *tri;
  976.     int nverts, ntris;
  977.     int i;
  978.  
  979. /* count verticies and triangles */
  980.     nverts = 0;
  981.     for( vert = verts; vert; vert = vert->next )
  982.     nverts++;
  983.  
  984.     ntris = 0;
  985.     for( tri = tris; tri; tri = tri->next )
  986.     ntris++;
  987.  
  988.     dprintf("makeoutput: vertexes in %d out %d\n",m->npolys*3,nverts);
  989.     dprintf("makeoutput: tris     in %d out %d\n",m->npolys,ntris);
  990.     (*m->ambegin)(nverts,ntris);
  991.  
  992.     for( i=0, vert = verts; vert; vert = vert->next, i++ ) {
  993.     vert->index = i;
  994.     (*m->amvertdata)(vert->id);
  995.     }
  996. }
  997.